package main

import (
	"fmt"
	. "local/algorithm/util"
	bst "local/datastructure/tree/binarySearchTree"
)

/*
*
解析

	双队列+层序遍历
	见![](http://cdn.bsummer.cn/20200122181942.png)
*/
func main() {
	t := bst.Generate([]int{10, 5, 15, 2, 8, 11, 17, 1, 4})
	w := widthOfBinaryTree(t)
	fmt.Println(w)
}

func widthOfBinaryTree(root *TreeNode) int {
	if root == nil {
		return 0
	}
	maxW := 1 //最大宽度

	//nqueue(node queue): 通过nqueue实现层序遍历 记录后续需遍历的节点
	//iqueue(node queue): 通过iqueue记录索引值实现宽度计算，记录后续需遍历的节点的索引值
	//size: 通过size来确定每一层的开始及结束，记录本层还剩节点数
	nqueue := []*TreeNode{}
	iqueue := []int{}
	nqueue = append(nqueue, root)
	iqueue = append(iqueue, 0) //根节点索引值认为是0

	size := 1
	for len(nqueue) != 0 { //层序遍历
		node := nqueue[0]
		nqueue = nqueue[1:]
		index := iqueue[0]
		iqueue = iqueue[1:]

		size-- //!!这里容易忘 一定要记得改动size!!

		if node.Left != nil {
			nqueue = append(nqueue, node.Left)
			iqueue = append(iqueue, 2*index+1)
		}

		if node.Right != nil {
			nqueue = append(nqueue, node.Right)
			iqueue = append(iqueue, 2*index+2)
		}

		if size == 0 { //表示该层遍历完了
			if len(iqueue) >= 2 { //因为maxW初始值为1，下一层至少有两个节点才有必要计算宽度 这里容易范错，比如直接有个节点root，其左右节点都是nil
				maxW = max(maxW, iqueue[len(iqueue)-1]-iqueue[0]+1) //iqueue[len(iqueue)-1]-iqueue[0]+1是下一层的宽度 (层中可能有空缺的节点，宽度不等同与该层连续节点数)
			}
			size = len(nqueue) //下一层的节点数
		}
	}

	return maxW
}

func max(a ...int) int {
	if len(a) == 1 {
		return a[0]
	}
	max := a[0]
	for _, v := range a {
		if v > max {
			max = v
		}
	}
	return max
}

func genereate() *TreeNode {
	l1 := &TreeNode{Val: 2}
	l2 := &TreeNode{Val: 1}
	l3 := &TreeNode{Val: 3}
	l1.Left = l2
	l1.Right = l3
	return l1
}

func inorderTraversal(root *TreeNode) []int {
	m := []int{}
	var helper func(root *TreeNode)
	helper = func(root *TreeNode) {
		if root == nil {
			return
		}
		helper(root.Left)
		m = append(m, root.Val)
		helper(root.Right)
	}

	helper(root)
	return m
}
